package leetcode_2101_2200;

import node.Node;

import java.util.*;

public class LeeCode_2101 {
    public static void main(String[] args) {
        System.out.println(maximumDetonation(new int[][]{{1,2,3},{2,3,1},{3,4,2},{4,5,3},{5,6,4}}));
//        System.out.println(maximumDetonation(new int[][]{{2, 1, 3}, {6, 1, 4}}));
//        System.out.println(maximumDetonation(new int[][]{{855,82,158},{17,719,430},{90,756,164},{376,17,340},
//                {691,636,152},{565,776,5},{464,154,271},{53,361,162},{278,609,82},{202,927,219},{542,865,377},
//                {330,402,270},{720,199,10},{986,697,443},{471,296,69},{393,81,404},{127,405,177}}
//));
    }
    private static int maximumDetonation(int[][] bombs) {
        int n = bombs.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long dis = (long) (Math.pow(bombs[i][1] - bombs[j][1], 2) + Math.pow(bombs[i][0] - bombs[j][0], 2));
                if (dis <= Math.pow(bombs[i][2], 2)){
                    if (map.containsKey(i)){
                        map.get(i).add(j);
                    }else {
                        List<Integer> list = new ArrayList<>();
                        list.add(j);
                        map.put(i, list);
                    }
                }
                if (dis <= Math.pow(bombs[j][2], 2)){
                    if (map.containsKey(j)){
                        map.get(j).add(i);
                    }else {
                        List<Integer> list = new ArrayList<>();
                        list.add(i);
                        map.put(j, list);
                    }
                }
            }
        }
        int ans = 0;
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            int count = 0;
            vis[i] = true;
            Deque<Integer> deque = new ArrayDeque<>();
            deque.add(i);
            while (!deque.isEmpty()){
                int size = deque.size();
                count += size;
                for (int j = 0; j < size; j++) {
                    Integer p = deque.pop();
                    if (!map.containsKey(p)){
                        continue;
                    }
                    for (Integer next : map.get(p)) {
                        if (vis[next]){
                            continue;
                        }
                        deque.offer(next);
                        vis[next] = true;
                    }
                }
            }
            Arrays.fill(vis, false);
            ans = Math.max(ans, count);
        }
        return ans;
    }
}